\section{Implementation}

The fixed-point algorithm has been implemented within the NetML
system
%\cite{netml2,atnac06,netml4design}.
The key code involved in
this fixed point iteration is shown in Figure \ref{fpimp}. This code
comes from the method \verb|LayeredFixedPoint()| of the network
class. The code has been simplified a little to avoid concerning
ourselves with details of no importance in this document.
\begin{figure}
\small
\begin{verbatim}
capdelta = 2*layeredFPConvgCrit;
iterations = 0;
while (capdelta>layeredFPConvgCrit
                && iterations<maxIterations) {
  for (l=nlayers-1;l>=0;l--) {
    layer[l].SetTraffic(layer[l+1].netLinks);
    layer[l].addRandomLinks();
    for (int sz=0;sz<=sizes;sz++)
      layer[l].calcRoutes(sz,flowsizes[sz]);
    layer[l].removeUnutilizedLinks();
    for (int sz=0;sz<=sizes;sz++)
      layer[l].calcRoutes(sz,flowsizes[sz]);
    layer[l].calcLoad();
    layer[l].calcLinkCosts();
  }
  capdelta = LayeredCapDelta();
  iterations ++;
}
\end{verbatim}
\caption{Fixed-point implementation}\label{fpimp}
\end{figure}

The implementation uses the methods, of the class \verb|network|, listed, with
explanations, in Table \ref{layermethods}.

\begin{table}
\begin{center}
\begin{tabular}{|p{3cm}|p{5cm}|}
\hline
\bf Method&\bf Purpose\\
\hline
\tt void LayeredFixedPoint()& This implements the fixed-point algorithm itself.\\
\tt void SetTraffic(vector links)& This method creates one traffic stream in the layer from
which it is called for each link in the vector of links supplied as a parameter.\\
\tt addRandomLinks()& This method adds virtual links to the layer from which it was called. These
links have a random origin and destination. They represent a ``trial'' tunnel through the layer below which will be kept only if it attracts sufficient traffic to be justified on a cost-benefit basis.\\
\tt void calcRoutes(int rt,double flowsize) & This method uses Dijkstra's algorithm to calculate
the shortest paths through the network, for the indicated flowsize, and then stores this information in the routing tables of the network.\\
\tt void removeUnutilizedLinks();& removes unutilized links.\\
\tt void calcLoad();& calculates the load on each link.\\
\tt void calcLinkCosts();& calculates the implied cost of each link, per unit traffic.\\
\hline
\end{tabular}
\caption{Methods of class network used in the fixed-point iteration}\label{layermethods}
\end{center}
\end{table}

\subsection{Implementation of Splitting and Merging}

The splitting and merging of traffic happens in the method \verb|calcLoad()|. The
key elements of this method are shown in Figure \ref{calcload}.

\begin{figure}
\small
\begin{verbatim}
public void calcLoad() {
    numTrafficstreams = netTrafficstreams.size(); // it changes dynalsplit.pdf: $(TEX1FILES) $(BIBFILES) $(GRAPHICSFILES) lsplit.aux lsplit.ind
mically
    int i;
    NetLink lnk;
    ListIterator li=netLinks.listIterator();
    if (!li.hasNext()) return;
    for (lnk=(NetLink)(li.next()); true; lnk=(NetLink)(li.next())) { // initialise each lnk
      lnk.setMean(0);
      lnk.setVar(0);
      lnk.setFlowRate(0.0);
      if (!li.hasNext()) break;
    }

    for (i=0;i<numTrafficstreams;i++) {
      for (int fs=0; fs<=sizes; fs++) {
        int org, dst, nxt;
        NetTrafficstream t = (NetTrafficstream)(netTrafficstreams.elementAt(i));
        if (!t.pareto && (t.flowSize()<flowsizes[fs]
           || (fs<sizes&&t.flowSize()>flowsizes[fs+1]))) continue;
        // skip till the right fs
        org = t.getOriginIndex();
        dst = t.getDestinationIndex();
        if (org==dst) continue;
        nxt = rtable[fs][org][dst];
        lnk = linktable[org][dst];
        while(nxt>=0){
          if (lnk!=null) {
            if (IamLayer && layerabove==null) {
                  lnk.addTraffic(t,fs>0?flowsizes[fs-1]:0,fs<sizes?flowsizes[fs]:0);
                } else {
                  lnk.addTraffic(t);
                }
        }
            if (nxt==dst) break;
            lnk = linktable[nxt][dst];
            nxt = rtable[fs][nxt][dst];
        }
      }
    }
    li=netLinks.listIterator();
    if (!li.hasNext()) return;
    for (lnk=(NetLink)(li.next()); true; lnk=(NetLink)(li.next())) {
            // initialise each lnk
        if (lnk.dynamic) {
          lnk.setCapacity(lnk.getMean());
        } else {
          lnk.setCapacity(lnk.getMean()+3*Math.sqrt(lnk.getVar()));
        }
        if (!li.hasNext()) break;
    }
    return;
}
\end{verbatim}
\caption{Method calcLoad}\label{calcload}
\end{figure}

\input{splittable.tex}

\section{Experiments}

The splitting formulae given in Section \ref{splitting} have been incorporated in the
fixed point algorithm from Section \ref{layeredfpoint} and the results are as follows.

